# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        h = len(nums) // 2
        root = TreeNode(nums[h])
        root.left = self.sortedArrayToBST(nums[:h])
        root.right = self.sortedArrayToBST(nums[h+1:])
        return root


def display(rt, dep=0):
    if not rt:
        return ''
    rtree = display(rt.right, dep+1)
    show = f'''{" " * dep}{rt.val}\n'''
    ltree = display(rt.left, dep+1)
    return rtree + show + ltree


solve = Solution()

questions = [
    ([-10, -3, 0, 5, 9], ),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    ans = solve.sortedArrayToBST(q[0])
    print(ans)
    print(display(ans))

